#coding:utf-8

'''
email: chenyan@feling.net

归并排序
'''

def merge(left, right):
    '''
    >>> merge([10,], [4,])
    [4, 10]

    >>> merge([2,7,13,20],[1,9,11,12])
    [1, 2, 7, 9, 11, 12, 13, 20]
    '''
    p_left = 0
    p_right = 0
    result = []
    while p_left<len(left) and p_right<len(right):
        if left[p_left]<right[p_right]:
            result.append(left[p_left])
            p_left += 1
        else:
            result.append(right[p_right])
            p_right += 1
    result += left[p_left:]
    result += right[p_right:]
    return result

def merge_sort(l):
    '''
    归并排序不能改变原列表，只是返回新的排序好的结果列表
    >>> a = list(range(30))
    >>> a.reverse()
    >>> merge_sort(a)
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
    >>> a
    [29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    '''

    if len(l)<=1: 
        return l
    left = merge_sort(l[:len(l)//2])
    right = merge_sort(l[(len(l)//2):])
    return merge(left, right)
    
if __name__=='__main__':
    import doctest
    doctest.testmod()

